The present invention relates to contents addressable memories. In particular although not exclusively the invention relates to contents addr as fully associative cache memories.
In the past retrieval of data stored in random access memory (RAM) has been carded out for example by algorithmic searching under the control of a microprocessor from outside the memory. Since only a small part of the RAM address space could be accessed at any one time it was necessary to sequence through all addresses until a match was found.
Contents addressable memory (CAM), on the other hand, allows the contents of a comparand register to be compared directly with all addresses held in its address space on a row by row basis. In some applications, however, it is quite likely that multiple matches will occur in a contents addressable memory, and it becomes necessary to recover a recognisable address by taking the match having the highest priority, which priority may be ascribed, for example, on the basis of position in the memory array. This is where a priority coder becomes important, and in many cases there is a need to look at a large number of match lines and potentially a large number of matches. One such scheme has utilised a tree of OR and NAND gates to select match outputs from rows which are local to each other, the resulting outputs being gated through further stages to establish a final priority match with its address. In such a scheme having, say, 512 match lines there would need to be some five stages of logic distributed across the depth of the array. Some schemes use a chain of gates in cascade with buffering and look-ahead inserted at appropriate points along the chain to minimise delays, while others adopt a parallel approach with multi-input gates. The problem with such schemes is that they are limited to small CAM structures if they are to perform quickly and not take up too much chip area.